/**
1. dp数组含义：dp[i][j]为背包重量为j时，从[0-i]元素中取得的最大元素和
2. 递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
3. 初始化：dp[i][0]初始化为0。dp[0][j]当j >= nums[0]时可以放入nums[0]
4. 遍历顺序：先遍历物品i，再遍历容量j
*/

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

// step 1# 求数组所有元素的和
int getSum(int* nums, int numsSize) {
    int sum = 0;
    int i;
    for(i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }
    return sum;
}

// step 2# 主函数，判断能否将数组分成和相等的两部分
bool canPartition(int* nums, int numsSize){
    // step 2.1# 计算总和
    int sum = getSum(nums, numsSize);

    // step 2.2# 如果总和为奇数，直接返回false
    if(sum % 2)
        return false;

    // step 2.3# 目标值是总和的一半
    int target = sum / 2;

    // step 2.4# 初始化dp数组，dp[i][j]表示前i个物品，容量为j的最大和
    int dp[numsSize][target + 1];
    memset(dp, 0, sizeof(int) * numsSize * (target + 1));  // 全部初始化为0

    int i, j;

    // step 2.5# 初始化第一行：如果j >= nums[0]，可以放入nums[0]
    for(j = nums[0]; j <= target; ++j) {
        dp[0][j] = nums[0];
    }

    // step 2.6# 遍历每个物品
    for(i = 1; i < numsSize; ++i) {
        // step 2.6.1# 遍历每个背包容量
        for(j = 1; j <= target; ++j) {
            if(j < nums[i]) {
                // step 2.6.1.1# 当前物品放不下，继承上一行的结果
                dp[i][j] = dp[i - 1][j];
            }
            else {
                // step 2.6.1.2# 取放与不放两种情况下的最大值
                dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j  - nums[i]] + nums[i]);
            }
        }
    }

    // step 2.7# 判断能否正好填满容量target
    return dp[numsSize - 1][target] == target;
}

